﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;
using System.Threading.Tasks;


namespace SearchText
{
    [Config(typeof(MyNoEmitConfig))]
    [MemoryDiagnoser]
    [Orderer(BenchmarkDotNet.Order.SummaryOrderPolicy.FastestToSlowest)]
    [RankColumn]
    public class UnsafeSearch
    {

        //string pattern = "aa bb cc"; // 模式串
        private readonly byte[] patternBytes = new byte[] { 0x61, 0x61, 0x20, 0x62, 0x62, 0x20, 0x63, 0x63 };//模式串的二进制数组
        private byte[] fileBytes;
        private string filePath = "Searcher2.bin";
        private static readonly int buffer_size = 1024;

        [GlobalSetup]
        public void Setup()
        {
            using (var stream = File.Open(filePath, FileMode.Open, FileAccess.Read))
            {
                fileBytes = new byte[stream.Length];
                stream.Read(fileBytes, 0, (int)stream.Length);
            }
        }

        //[Benchmark]
        [Benchmark(Baseline = true)]
        public unsafe void UnsafeFind()
        {


            List<int> positions = new List<int>();
            fixed (byte* pFileBytes = fileBytes)
            fixed (byte* pPatternBytes = patternBytes)
            {
                byte* pFile = pFileBytes;
                byte* pPattern = stackalloc byte[patternBytes.Length];
                int patternLength = patternBytes.Length;

                for (int i = 0; i <= fileBytes.Length - patternLength; i++)
                {
                    byte* pCurrent = pFile + i;
                    byte* pPatternCurrent = pPattern;
                    int match = 1;

                    for (int j = 0; j < patternLength; j++)
                    {
                        if (*pCurrent++ != *pPatternCurrent++)
                        {
                            match = 0;
                            break;
                        }
                    }

                    if (match == 1)
                    {
                        positions.Add(i);
                    }
                }
            }
        }

        [Benchmark]
        //暴力搜索
        public List<int>  Search()
        {
            List<int> positions2 = new List<int>();
            int patternLength = patternBytes.Length;

            for (int i = 0; i <= fileBytes.Length - patternLength; i++)
            {
                int match = 1;

                for (int j = 0; j < patternLength; j++)
                {
                    if (fileBytes[i + j] != patternBytes[j])
                    {
                        match = 0;
                        break;
                    }
                }

                if (match == 1)
                {
                    positions2.Add(i);
                }
            }
            return positions2;
        }




        [Benchmark]
        //KMP
        public List<long> KMPSearch()
        {
            List<long> positions3 = new List<long>();
            int patternLength = patternBytes.Length;
            int[] lps = new int[patternLength]; // Longest Prefix Suffix array
            ComputeLPSArray(patternLength, lps); // Compute the LPS array

            long bytesRead = 0;
            int j = 0;

            for (int i = 0; i < fileBytes.Length; i++)
            {
                while (j > 0 && fileBytes[i] != patternBytes[j])
                {
                    j = lps[j - 1];
                }

                if (fileBytes[i] == patternBytes[j])
                {
                    j++;
                }

                if (j == patternLength)
                {
                    positions3.Add((long)i - (patternLength - 1));
                    j = lps[j - 1];
                }
            }
            return positions3;
        }

        private void ComputeLPSArray(int patternLength, int[] lps)
        {
            int len = 0;
            lps[0] = 0; // lps[0] is always 0

            int i = 1;
            int j = 0;

            while (i < patternLength)
            {
                if (patternBytes[i] == patternBytes[j])
                {
                    j++;
                    lps[i] = j;
                    i++;
                }
                else
                {
                    if (j != 0)
                    {
                        j = lps[j - 1];
                    }
                    else
                    {
                        lps[i] = 0;
                        i++;
                    }
                }
            }
        }
        //unsafe的KMP算法
        [Benchmark]
        public unsafe List<long> UnsafeKMPSearch()
        {
            List<long> positions3 = new List<long>();
            int patternLength = patternBytes.Length;
            int* next = stackalloc int[patternLength]; // 使用stackalloc分配内存
            UnsafeComputeNEXTArray(patternLength, next);

            long bytesRead = 0;
            int j = 0;

            for (int i = 0; i < fileBytes.Length; i++)
            {
                while (j > 0 && fileBytes[i] != patternBytes[j])
                {
                    j = next[j - 1];
                }

                if (fileBytes[i] == patternBytes[j])
                {
                    j++;
                }

                if (j == patternLength)
                {
                    positions3.Add((long)i - (patternLength - 1));
                    j = next[j - 1];
                }
            }
            return positions3;
        }

        private unsafe void UnsafeComputeNEXTArray(int patternLength, int* next)
        {
            int len = 0;
            next[0] = 0;
            int i = 1;
            int j = 0;

            while (i < patternLength)
            {
                if (patternBytes[i] == patternBytes[j])
                {
                    j++;
                    next[i] = j;
                    i++;
                }
                else
                {
                    if (j != 0)
                    {
                        j = next[j - 1];
                    }
                    else
                    {
                        next[i] = 0;
                        i++;
                    }
                }
            }

        }

        //字符串搜索
        [Benchmark]
        public List<int> PositionsInString()
        {
            List<int> positions4 = new List<int>();
            // 将字节数组转换为UTF-8编码的字符串
            string fileString = Encoding.UTF8.GetString(fileBytes);
            string patternString= Encoding.UTF8.GetString(patternBytes);
            //if (string.IsNullOrEmpty(patternString) || string.IsNullOrEmpty(fileString))
            //{
            //    return 0; // 如果模式字符串或文件字符串为空，则不执行搜索
            //}

            int index = fileString.IndexOf(patternString);
            while (index >= 0)
            {
                positions4.Add(index);
                index = fileString.IndexOf(patternString, index + patternString.Length); // 继续搜索下一个匹配项
            }
            return positions4;
            //    int index = 0;
            //    while ((index = fileString.IndexOf(patternString, index)) != -1)
            //    {
            //        positions4.Add(index);
            //        index += patternString.Length; // 移动到找到的模式之后，继续搜索
            //        if (index >= fileString.Length) break; // 确保不超出字符串长度
            //    }
            //return positions;
        }


    }
}